package java学习.代码随想录.动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/4 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 买卖股票的最佳时机IV {
    /**      dp[i天数][是否持有股票][卖出的次数]
     * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
     * 0 不操作
     * 1 买第一次
     * 2 卖第一次
     * 3 买第二次
     * 4 卖第二次
     *
     * 5 买第三次
     * 6 卖第三次
     *  发现规律 ，除了0以外，偶数就是卖出，奇数就是买入。
     * dp[i天数][状态]
     *
     * dp[0][0] = 0;
     * dp[0][1] =  -price[i];
     * dp[0][3]  =  -price[i];
     *
     * dp[i][1] = dp[i-1][1], dp[i][0]-price[i];
     * dp[i][2] = dp[i-1][2], dp[i-1][1]+price[i];
     * dp[i][3] = dp[i-1][3], dp[i-1][2]-price[i];
     * dp[i][4] = dp[i-1][4], dp[i-1][3]+price[i];
     */
    public static int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int count = 2*k+1;
        int[][] dp = new int[n][count];

        dp[0][0] = 0;
//        dp[0][1] = prices[0]; 1 3 5 7 9
        for (int i = 1; i < count; i+=2) {
            dp[0][i]  = -prices[0];
        }

        for (int i = 1; i < n; i++) {

            for (int j = 1; j < count; j+=2) {
                dp[i][j]  =Math.max(dp[i-1][j],dp[i-1][j-1] - prices[i]);
                dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
            }
        }
        return dp[n-1][count-1];
    }

    public static void main(String[] args) {
//        prices = [3,3,5,0,0,3,1,4] 输出：6
        int [] test = {3,3,5,0,0,3,1,4};
//        k = 2, prices = [3,2,6,5,0,3]
        int [] arr = {3,2,6,5,0,3};
        System.out.println(maxProfit(2,arr));
//        System.out.println(maxProfit2(test));
    }

}
